package leetcode.code2121;

import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;

public class Solution implements IDebug {

	public long[] getDistances(int[] arr) {
		int len = arr.length;
		long[] ans = new long[len];
		// long[]{索引，数量，索引位置累加和};
		Map<Integer, long[]> infos = new HashMap<>();
		for (int i = 0; i < len; i++) {
			int cur = arr[i];
			if (infos.containsKey(cur)) {
				long[] info = infos.get(cur);
				long index = info[0], size = info[1], sum = info[2];
				long curSum = sum + (i - index) * size;
				infos.put(cur, new long[] { i, size + 1, curSum });
				ans[i] = curSum;
			} else {
				infos.put(cur, new long[] { i, 1, 0 });
			}
		}
		infos = new HashMap<>();
		for (int i = len - 1; i >= 0; i--) {
			int cur = arr[i];
			if (infos.containsKey(cur)) {
				long[] info = infos.get(cur);
				long index = info[0], size = info[1], sum = info[2];
				long curSum = sum + (index - i) * size;
				infos.put(cur, new long[] { i, size + 1, curSum });
				ans[i] += curSum;
			} else {
				infos.put(cur, new long[] { i, 1, 0 });
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
